package com.exercises;


import com.alibaba.fastjson.JSONObject;

import java.util.Stack;

class Exercise279 {
    public static void main(String[] args) {
        System.out.println(new Exercise279().numSquares(12));
    }

    int[] dp = null;

    public int numSquares(int n) {
        dp = new int[n + 1];
//        return dfs(n);
        for (int i = 1; i <= n; i++) {
            Integer min = Integer.MAX_VALUE;
            for (int j = 1; i >= j * j; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }

    public int dfs(int n) {
        if (dp[n] != 0) {
            return dp[n];
        } else {
            int sqrt = (int) Math.sqrt(n);
            int less = n - sqrt * sqrt;
            if (less == 0) {
                dp[n] = 1;
            } else {
                int result = Integer.MAX_VALUE;
                for (int i = 1; i <= sqrt; i++) {
                    result = Math.min(result, dfs(i * i) + dfs(n - i * i));
                }
                dp[n] = result;
            }
            return dp[n];
        }
    }


}

